package org.czl.leetCode3;

public class l1463 {
        public int cherryPickup(int[][] grid) {
            int n = grid.length;
            int[][][] dp = new int[2*n + 1][n + 1][n + 1];
            for(int i = 0; i < 2*n + 1; i++){
                for(int j = 0; j <= n; j++){
                    for(int k = 0; k <= n; k++){
                        dp[i][j][k] = Integer.MIN_VALUE;
                    }
                }
            }
            dp[2][1][1] = grid[0][0];
            for(int i = 3; i < 2*n + 1; i++){
                for(int x1 = 1; x1 <= n; x1++){
                    for(int x2 = 1; x2 <= n; x2++){
                        int y1 = i - x1; int y2 = i - x2;
                        if(y1 <= 0 || y1 > n || y2 <= 0 || y2 > n){
                            continue;
                        }
                        //当前格子的得分 要是等于-1的话 表示当前格子是荆棘 不需要计算
                        int A = grid[x1 - 1][y1 - 1]; int B = grid[x2 - 1][y2 - 1];
                        if(A == -1 || B == -1)continue;
                        int a = dp[i - 1][x1 - 1][x2];
                        int b = dp[i - 1][x1][x2 - 1];
                        int c = dp[i - 1][x1][x2];
                        int d = dp[i - 1][x1 - 1][x2 - 1];
                        int t = Math.max(Math.max(a, b), Math.max(c, d)) + A;
                        if(x1 != x2){
                            t += B;
                        }
                        dp[i][x1][x2] = t;
                    }
                }
            }
            return dp[2*n][n][n] <= 0 ? 0 : dp[2*n][n][n];
        }
    }

